/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年11月26日
*   描    述：
*   
================================================================*/


#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int right = nums.size() - 1, left = 0;
        int pos = 0;
        while( true ){
            pos = partition(nums, left, right);
            if( pos == k - 1 )
                return nums[pos];
            if( pos < k - 1 ){
                left = pos;
            }else
                right = pos;
        }
    }

private:
    int partition(vector<int>& nums, int left, int right){
        int pri = right--;
        int tmp = nums[pri];
        while( left < right ){
            while( left < right && nums[left] > tmp )
                left++;
            nums[right] = nums[left];

            while( left < right && nums[right] <= tmp )
                right--;
            nums[left] = nums[right];
        }

        nums[left] = tmp;
        return left;
    }

};
